package tree.BinarySearchTree;

import tree.TreeNode;

/**
 * @ClassName convertBST
 * @Description TODO
 * @Author lenovo
 * @Date 2023-04-20 10:49
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class convertBST {
    /**
     * 538. 把二叉搜索树转换为累加树
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * <p>
     * 提醒一下，二叉搜索树满足下列约束条件：
     * <p>
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     * 左右子树也必须是二叉搜索树。
     * <p>
     * 其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。
     *     5                    18
     * 2      13            20      13
     */
    int sum;

    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        depth(root);
        return root;
    }

    private void depth(TreeNode root) {
        if (root == null) {
            return ;
        }
        depth(root.right);
        sum += root.val;
        root.val=sum;
        depth(root.left);
    }

    public static void main(String[] args) {

        TreeNode treeNode = new TreeNode(3);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(4);

        convertBST convertBST = new convertBST();
        TreeNode treeNode1 = convertBST.convertBST(treeNode);
        System.out.println(treeNode1);
    }
}